package hot;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class yisiba {
//    https://leetcode.cn/problems/sort-list/solutions/13728/sort-list-gui-bing-pai-xu-lian-biao-by-jyd/?envType=study-plan-v2&envId=top-100-liked
     static class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }


        public static ListNode sortList(ListNode head) {
            ListNode cur=head;
            List<Integer> ret=new ArrayList<>();
            while(cur!=null){
                ret.add(cur.val);
                cur=cur.next;

            }
            int[] nums=ret.stream().mapToInt(Integer::intValue).toArray();
            Arrays.sort(nums);
            //将排序后的数组，进行尾插即可
            ListNode newHead=new ListNode(-1);
             cur=newHead;
            int i=0;
            while(i<nums.length){
                ListNode node=new ListNode(nums[i]);
                cur.next=node;
                cur=node;
                i++;
            }
            return newHead.next;
        }

    public static void main(String[] args) {
        ListNode listNode1=new ListNode(4);
        ListNode listNode2=new ListNode(2);
        ListNode listNode3=new ListNode(1);
        ListNode listNode4=new ListNode(3);
        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        listNode4.next=null;
        ListNode listNode = sortList(listNode1);


    }
    //使用归并排序去解决排序链表这道题
//    https://leetcode.cn/problems/sort-list/?envType=study-plan-v2&envId=top-100-liked
    class Solution {
        public ListNode sortList(ListNode head) {
            //使用归并排序来进行解决
            // if(head==null){
            //     return null;
            // }
            return mergesort(head);
        }
        public ListNode mergesort(ListNode head){
            if(head==null||head.next==null){
                return head;
            }
            //利用快慢指针找链表的中间节点
            ListNode mid=findmiddle(head);
            //分割为2快链表
            ListNode rightHead=mid.next;
            //讲左边的链表置为空
            mid.next=null;
            ListNode l1=mergesort(head);
            ListNode l2=mergesort(rightHead);
            return mergeTwoList(l1,l2);
        }
        public ListNode findmiddle(ListNode head){
            ListNode fast=head;
            ListNode slow=head;
            while(fast.next!=null&&fast.next.next!=null){
                fast=fast.next.next;
                slow=slow.next;
            }
            return slow;

        }
        //合并两个有序链表
        public ListNode mergeTwoList(ListNode l1,ListNode l2){
            if(l1==null){
                return l2;
            }
            if(l2==null){
                return l1;
            }
            ListNode newHead=new ListNode(-1);
            ListNode cur=newHead;
            while(l1!=null&&l2!=null){
                if(l1.val>l2.val){
                    cur.next=l2;
                    cur=l2;
                    l2=l2.next;
                }else{
                    cur.next=l1;
                    cur=l1;
                    l1=l1.next;
                }
            }
            if(l1!=null){
                cur.next=l1;
            }
            if(l2!=null){
                cur.next=l2;
            }
            return newHead.next;
        }
    }
    }

